package problems.practice;

/**
 * 2179. 统计数组中的好三元组数目
 * <p></p>
 *
 * @author habitplus
 * @since 18:38, 2022/10/4
 */
public class T2179 {
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] p = new int[n];
        // 建立到下标的映射
        for (int i = 0; i < n; ++i) p[nums1[i]] = i;

        // 树状数组
        int[] tree = new int[n + 1];
        long ans = 0L;
        int less, y;

        for (int i = 1; i < n - 1; ++i) {
            // 将 p[nums2[i-1]] + 1 加入树状数组
            for (int j = p[nums2[i - 1]] + 1; j <= n; j += j & -j)
                ++tree[j];

            y = p[nums2[i]];
            less = 0;
            // 计算 less
            for (int j = y; j > 0; j &= j - 1) less += tree[j];

            ans += (long) less * (n - 1 - y - (i - less));
        }
        return ans;

    }
}
